# !/usr/bin/env python
# -*- coding: utf-8 -*-
# ------------------------------
'''
n 位格雷码序列 是一个由 2^n 个整数组成的序列，其中：
每个整数都在范围 [0, 2^n - 1] 内（含 0 和 2n - 1）
第一个整数是 0
一个整数在序列中出现 不超过一次
每对 相邻 整数的二进制表示 恰好一位不同 ，且
第一个 和 最后一个 整数的二进制表示 恰好一位不同
给你一个整数 n ，返回任一有效的 n 位格雷码序列 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/gray-code
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
'''
# A建类
class Solution(object):
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        gelei_list = []
        flag = 0
        # print(tem_list)
        if n == 1:
            gelei_list = [0, 1]
            return gelei_list
        else:
            gelei_list = [0, 1]
            for i in range((2**n)-2):
                flag = 0
                tem = gelei_list[i] ^ gelei_list[i+1]
                # print(i)
                for j in range(2**n):
                    flag = 0
                    if j == gelei_list[i+1]:
                        # print(gelei_list[i+1])
                        continue
                    elif (j ^ gelei_list[i+1]) & tem == 0:
                        for z in gelei_list:
                            if z == j:
                                flag = 1
                        if flag != 1:
                            gelei_list.append(j)
                            break
                # print(gelei_list)
            return gelei_list

    def main(self):
        '''
        逻辑控制函数
        '''
        n = int(input('请输入n (0-2^n-1的格雷码)：'))
        results = self.grayCode(n)
        print(results)
if __name__ == '__main__':
    solution = Solution()
    solution.main()
